|
|
Redukce nedeterministických konečných automatů
Procházka, Lukáš ; Kořenek, Jan (oponent) ; Kaštil, Jan (vedoucí práce)
Nedeterministický konečný automat je důležitým nástrojem, který se používá pro zpracování řetězců v mnoha různých oblastech programování. V rámci zvýšení efektivity programů je důležité snažit se o zmenšování jeho velikosti. Tento problém je však velmi výpočetně náročný, proto je potřeba hledat nové postupy. V této práci jsou uvedeny základy konečných automatů a poté jsou představeny různé metody zabývající se jejich redukcí. Použitelné redukční algoritmy jsou v práci podrobněji popsány, dále implementovány a otestovány. Nakonec jsou výsledky zhodnoceny.
|
|
|
Optimalizace žebra na křídle letounu
Kopřiva, Lubomír ; Suchánek, Miroslav (oponent) ; Petruška, Jindřich (vedoucí práce)
Topologická optimalizace je metoda poskytující nový směr v navrhování technických objektů. Cílem topologické optimalizace je stanovení optimálního rozložení materiálu v návrhovém prostoru. Tato diplomová práce je zaměřená na optimalizaci žebra č.6 v křídle letounu EV-55 užitím softwaru HW/OptiStruct 7.0 obsaženého v softwarovém balíku HyperWorks 7.0. Optimalizace žebra byla počítána ve čtyřech rozdílných zatěžovacích případech. Výsledné tvary žebra byly testovány pevnostním výpočtem v softwaru ANSYS 10.0. Nakonec byla získaná data hmotností optimalizovaných žeber porovnána s hmotností žebra původního.
|
|
| |
|
|
Reducing Size of Nondeterministic Automata with SAT Solvers
Šedý, Michal ; Havlena, Vojtěch (oponent) ; Holík, Lukáš (vedoucí práce)
Nondeterministic finite automata (NFA) are widely used in computer science fields, such as regular languages in formal language theory, high-speed network monitoring, image recognition, hardware modeling, or even in bioinformatic for the detection of the sequence of nucleotide acids in DNA. They are also used in regular mode checking, in string solving, in verification of pointer manipulating programs, for construction of linear arithmetic equations and inequalities, for decision in WS1S and WS2S logic, and many others. Automata minimization is a fundamental technique that helps to decrease resource claims (memory, time, or a number of hardware components) of implemented automata and speed up automata operations. Commonly used minimization techniques, such as state merging, transition pruning, and saturation, can leave potentially minimizable automaton subgraphs with duplicit language information. These fragments consist of a group of states, where the part of language of one state is piecewise covered by the other states in this group. The thesis describes a new minimization approach, which uses SAT solver, which provides information for efficient minimization of these so far nonminimizable automaton parts. Moreover, the newly investigated method, which only uses solver information and state merging, can minimize the automaton similarly and on automata with low transition count faster than a tool RABIT/Reduce, which uses state merging and transition pruning.
|
|
|
Možnosti minimalizace indukovaného odporu
Skarolek, Vilém ; Kouřil, Martin (oponent) ; Lajza, Ondřej (vedoucí práce)
Indukovaný odpor tvoří podstatnou část celkového odporu letounu při letu a tak jeho minimalizace je žádoucí při snaze o hospodárný provoz letecké dopravy. Bakalářská práce se zabývá možnostmi minimalizace indukovaného odporu. První čast této práce se zabývá úvodem do problému tvorby indukovaného odporu za letu. V druhé části je zpracován přehled možných způsobů minimalizace, jejich popis, konstrukční provedení včetně zhodnocení jednotlivých metod minimalizace.
|
|
|
Efficient Automata Techniques and Their Applications
Havlena, Vojtěch ; Jančar, Petr (oponent) ; Mayr, Richard (oponent) ; Esparza, Javier (oponent) ; Vojnar, Tomáš (vedoucí práce)
This thesis develops efficient techniques for finite automata and their applications. In particular, we focus on finite automata in network intrusion detection and automata in decision procedures and verification. In the first part of the thesis, we propose techniques of approximate reduction of nondeterministic automata decreasing consumption of resources of hardware-accelerated deep packet inspection. The second part is devoted to automata in decision procedures, in particular, to weak monadic second-order logic of k successors (WSkS) and the theory of strings. We propose a novel decision procedure for WS2S based on automata terms allowing one to effectively prune the state space. Further, we study techniques of WSkS formulae preprocessing intended to reduce the sizes of constructed intermediate automata. Moreover, we employ automata in a decision procedure of the theory of strings for efficient handling of the proof graph. The last part of the thesis then proposes optimizations in rank-based Buchi automata complementation reducing the number of generated states during the construction.
|
|
|
Evoluční resyntéza kombinačních obvodů
Pták, Ondřej ; Schwarz, Josef (oponent) ; Sekanina, Lukáš (vedoucí práce)
Tato práce se zabývá kombinačními číslicovými obvody a jejich optimalizací. Nejprve jsou představeny hlavní úrovně abstrakce používané při návrhu kombinačních číslicových obvodů. Následně jsou prozkoumány různé metody pro optimalizaci kombinačních číslicových obvodů. Další část této práce je věnována především evolučním algoritmům, jejich společným rysům a variantám: genetickým algoritmům, evolučním strategiím, evolučnímu programování a genetickému programování. Podrobně je popsána varianta genetického programování nazývaná kartézské genetické programování (CGP) a využití CGP v různých oblastech, zejména při syntéze či optimalizaci kombinačních číslicových obvodů. Také jsou představeny některé modifikace CGP a problém škálovatelnosti evolučního návrhu obvodů. V navazující části je popsána metoda pro evoluční resyntézu kombinačních číslicových obvodů. Nejprve je popsán návrh, zejména způsob dělení obvodu na podobvody, poté implementační detaily a nakonec experimenty s touto metodou a jejich výsledky.
|
|
|
Minimalizace operačního systému CentOS
Vashkevich, Pavel ; Caha, Tomáš (oponent) ; Komosný, Dan (vedoucí práce)
Účelem této práce je provést redukci operačního systému Linux. Pro minimalizaci byla zadaná linuxová distribuce CentOS 8, která je vytvořena na základě otevřených zdrojových kódů. Tyto jsou šířeny společností Red Hat. Teoretická část práce popisuje základní součásti operačního systému, mezi které patří linuxové jádro, ovladače a grafické rozhraní. Praktická část popisuje návrh metody pro minimalizaci operačního systému. Tato metoda zahrnuje i porovnání minimalistických webových prohlížečů. Výsledná velikost po provedení redukce je 731 MB. Software pro automatizaci minimalizace je zveřejněn v osobním repozitáře na GitHub pod licencí MIT.
|
|
|
Knihovna operací nad konečnými automaty
Bartůněk, Petr ; Puš, Viktor (oponent) ; Kaštil, Jan (vedoucí práce)
Tato práce se zabývá dvěma základními operacemi nad konečnými automaty. Determinizací nedeterministických konečných automatů a minimalizací deterministických konečných automatů. Pro obě tyto operace jsem navrhoval sekvenční algoritmy, které jsou paralelizovatelné. Zabývám se hledáním zrychlení především pomocí SSE instrukcí nebo pomocí knihovny openMP. Trendem dnešní doby je především zvyšování počtu procesorů, proto budu navrhovat paralelní algoritmy pro více procesorů. Při hledání optimálního řešení budu zkoumat další možnosti, jak dosáhnout zrychlení, např. efektivním uložením datových struktur v paměti.
|
|
|
Korektor diakritiky
Veselý, Lukáš ; Sumec, Stanislav (oponent) ; Smrž, Pavel (vedoucí práce)
Cílem předkládané práce je návrh a implementace aplikace, umožňující doplňování a naopak odstranění diakritiky v česky psaném textu. Popsána je použitá vyhledávací struktura trie a její vztah s konečnými automaty. Dále je předveden algoritmus minimalizace konečného automatu a diskutovány různé metody pro doplňování diakritiky. V praktické části je uvedena samotná implementace programu v programovacím jazyce Java s využitím objektově orientovaného přístupu. Na závěr je provedeno vyhodnocení a analýza dosažených výsledků.
|
host ::
RSS.